重建二叉树

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

例如，给出

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树：

    3
   / \
  9  20
    /  \
   15   7

分析

前序遍历的性质:

节点按照 [ 根节点 | 左子树 | 右子树 ] 排序

中序遍历性质:

节点按照 [ 左子树 | 根节点 | 右子树 ] 排序

因为前序的第一个是根节点, 而中序中, 根节点将树分成了左子树和右子树, 于是可以得到左右子树的中序遍历序列。

根据得到的下标位置， 得到左子树的长度，从而在前序遍历中找到下一个左子树的根节点(右子树, 同理)

root 的 位置 i

左子树

• 根节点: root + 1
• 左边界: left
• 右边界: i - 1

右子树

• 根节点: i - left + root + 1
• 左边界: i + 1
• 右边界: right

代码

var buildTree = function(preorder, inorder) {
    let map = new Map()
    for(let i=0;i<preorder.length;i++){
        map.set(inorder[i],i)
    }
    const myBuildTree=(root,left,right)=>{
        // node
        if(left > right) return null
        let node = new TreeNode(preorder[root])
        let i = map.get(preorder[root])
        // 左子树
        node.left = myBuildTree(root+1,left,i-1)
        node.right = myBuildTree(i-left+root+1,i+1,right)
        return node
    }
    return myBuildTree(0,0,preorder.length-1)
};